package com.ming.learn.from.carl.binary.tree;

import com.ming.commons.utils.TreeNode;

import java.util.Stack;

/*
404.左叶子之和
 */
public class Of20210312LeetCode404 {
    /*
    404.左叶子之和
     */
    public static void main(String[] args) {
        System.out.println(sumOfLeftLeaves2(new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15),
                new TreeNode(7)))));
    }

    /*
    递归
     */
    private static int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int midValue = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) {
            midValue = root.left.val;
        }
        return midValue + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }

    /*
   迭代法
     */
    private static int sumOfLeftLeaves2(TreeNode root) {
        if (root == null) return 0;
        int result = 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node.left != null && node.left.left == null && node.left.right == null) result += node.left.val;
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return result;
    }
}
